import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-04-08
 * Time: 12:36
 */
public class test1 {
    public boolean checkValidString(String s) {
        // 用一个栈存储括号
        Stack<Integer> s1 = new Stack<>();
        // 一个栈存储*号
        Stack<Integer> s2 = new Stack<>();
        int n = s.length();
        for(int i=0;i<n;i++){
            char c = s.charAt(i);
            if(c=='('){
                s1.push(i);
            }else if(c=='*'){
                s2.push(i);
                // 右括号
            }else{
                if(!s1.isEmpty()){
                    s1.pop();
                }else if(!s2.isEmpty()){
                    s2.pop();
                }else{
                    return false;
                }
            }
        }
        // 左括号还有剩余，*作为右括号
        while(!s1.isEmpty() && !s2.isEmpty()){
            int leftIndex = s1.pop();
            int starIndex = s2.pop();
            if(leftIndex>starIndex){
                return false;
            }
        }
        return s1.isEmpty();
    }
}
